class Solution(object):
    def kthSmallestProduct(self, nums1, nums2, k):
        n1 = len(nums1)
        n2 = len(nums2)
        neg1 = 0
        zero1 = 0
        pos1 = 0
        neg2 = 0
        zero2 = 0
        pos2 = 0
        for num in nums1:
            if num < 0:
                neg1 += 1
            if num == 0:
                zero1 += 1
            if num > 0:
                pos1 += 1
        for num in nums2:
            if num < 0:
                neg2 += 1
            if num == 0:
                zero2 += 1
            if num > 0:
                pos2 += 1
        neg_count = neg1 * pos2 + neg2 * pos1
        zero_count = zero1 * n2 + zero2 * n1 - zero1 * zero2
        pos_count = neg1 * neg2 + pos1 * pos2
        if k <= neg_count:
            state = 0
        if neg_count < k <= neg_count + zero_count:
            return 0
        if k > neg_count + zero_count:
            state = 1
            k = k - neg_count - zero_count
        def cal(val, state):
            ans = 0
            if state == 0:
                index0 = 0
                index1 = neg2 + zero2
                while index0 < neg1 and index1 < n2:
                    if nums1[index0] * nums2[index1] > val:
                        ans += neg1 - index0
                        index1 += 1
                    else:
                        index0 += 1
                index0 = neg1 + zero1
                index1 = 0
                while index0 < n1 and index1 < neg2:
                    if nums1[index0] * nums2[index1] > val:
                        ans += neg2 - index1
                        index0 += 1
                    else:
                        index1 += 1
                return ans <= neg_count - k
            else:
                index1 = neg1 + zero1
                index2 = n2 - 1
                while index1 < n1 and index2 >= neg2 + zero2:
                    if nums1[index1] * nums2[index2] > val:
                        ans += n1 - index1
                        index2 -= 1
                    else:
                        index1 += 1
                index1 = neg1 - 1
                index2 = 0
                while index1 >= 0 and index2 < neg2:
                    if nums1[index1] * nums2[index2] > val:
                        ans += index1 + 1
                        index2 += 1
                    else:
                        index1 -= 1
                return ans <= pos_count - k
            


        if state == 0:
            left = - 10 ** 10
            right = 0
            while left < right:
                mid = (left + right) // 2
                if cal(mid, 0):
                    right = mid
                else:
                    left = mid + 1
        else:
            left = 0
            right = 10 ** 10
            while left < right:
                mid = (left + right) // 2
                if cal(mid, 1):
                    right = mid
                else:
                    left = mid + 1
        return left
data = Solution()
nums1 = [2,5]
nums2 = [3,4]
k = 2
print(data.kthSmallestProduct(nums1, nums2, k))
